//二叉树的前序遍历
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
       int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };

int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    else
        return 1+TreeSize(root->left)+TreeSize(root->right);
}

void prevTree(struct TreeNode* root,int* a,int* n)
{
    if(root==NULL)
        return ;
    a[(*n)]=root->val;
    (*n)++;
    prevTree(root->left,a,n);
    prevTree(root->right,a,n);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    int num=TreeSize(root);
    *returnSize=num;
    if(num==0)
        return NULL;
    int n=0;
    int* a=(int*)malloc(sizeof(int)*num);
    prevTree(root,a,&n);
    return a;
    
}

//判断是否为另一颗树的子树
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
        return true;
    if(p==NULL&&q!=NULL)
        return false;
    if(q==NULL&&p!=NULL)
        return false;
    if(q->val!=p->val)
        return false;
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root==NULL&&subRoot==NULL)
        return true;
    if(root==NULL&&subRoot!=NULL)
        return false;
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

//判断是否为平衡二叉树
//方法2时间复杂度为（O(N*N))
int TreeDepth(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    int rightDepth=TreeDepth(root->right);
    int leftDepth=TreeDepth(root->left);
    return(rightDepth>leftDepth?rightDepth:leftDepth)+1;
}

bool isBalanced(struct TreeNode* root) {
    if(root==NULL)
        return true;
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    if(TreeDepth(root->left)-rightDepth>1||rightDepth-leftDepth>1)
        return false;
    return isBalanced(root->left)&&isBalanced(root->right);
}

//方法2时间复杂度为（O(N）
bool _isBalanced(struct TreeNode* root,int* pdepth)
{
    if(root==NULL)
    {
        *pdepth=0;
        return true;
    }
    else
    {
        int leftdepth=0;
        if(_isBalanced(root->left,&leftdepth)==false)
            return false;
        
        int rightdepth=0;
        if(_isBalanced(root->right,&rightdepth)==false)
            return false;

        if(abs(leftdepth-rightdepth) >1)
            return false;

        *pdepth = leftdepth > rightdepth ? leftdepth+1 : rightdepth+1;
        return true;
    }
}

bool isBalanced(struct TreeNode* root) {
    int depth=0;
    return _isBalanced(root,&depth);
}

//二叉树的遍历
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
 }TreeNode;

TreeNode* createTree(char* str,int* pi)
{
    if(str[(*pi)]=='#')
    {
        (*pi)++;
        return NULL;
    }
    else {
    TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode));
    root->val=str[(*pi)];
    (*pi)++;
    root->left=createTree(str, pi);
    root->right=createTree(str, pi);
    return root;  
    }
     
}

void inTree(TreeNode* root)
{
    if(root==NULL)
        return;
    inTree(root->left);
    printf("%c ",root->val);
    inTree(root->right);
}



int main() {
    char str[100]={0};
    scanf("%s",str);
    int i=0;
    TreeNode* root=createTree(str,&i);
    inTree(root);
    return 0;
}


